The present invention relates generally to computer memory management and more specifically to techniques for caching segment descriptors.
The memory management (virtual memory) system of a computer is responsible for translating the virtual (logical) addresses viewed by the programmer to the physical addresses used to reference main memory (hereinafter referred to as "memory"). This specification will focus on aspects of the memory management system of the industry standard x86 processor architecture. However, it will be apparent to one of ordinary skill in the art that the invention disclosed herein is applicable to other processor architectures involving retrieval of segment descriptors from memory.
Translation of virtual addresses to physical addresses in the x86 memory management scheme involves both segmentation and paging. Segmentation is the process by which virtual addresses are mapped to intermediate addresses. Paging is the process by which intermediate addresses are mapped to physical addresses. Except for degenerate cases, the intermediate address will be different from the original virtual address. Similarly, except when paging is disabled, the physical address will be different from the associated intermediate address. When paging is disabled, the intermediate and physical addresses are identical.
Segmentation
The x86 Architecture encourages the division of programs into modules referred to as segments. There can be many segments. In essence, the segment is its own address space. Intra-segment addressing can be oblivious to the fact that the segment is not necessarily located at the bottom of the intermediate address space. Within a segment, locations are referenced using an Offset that is a measure of the distance of the location relative to the bottom of the segment. The bottom of the segment is the segment base.
Every segment has an associated segment descriptor. The segment descriptor has attributes that describe the segment. Two very important components of a segment descriptor are the segment base address and the segment limit. The segment base address identifies the location within the intermediate address space at which the segment begins. The segment limit is used to define the maximum Offset allowed and thereby the size of the segment.
A particular segment is identified using a 13-bit (Segment) Index and a 1-bit (Segment) Table Indicator (TI). The TI identifies which of two tables, the Global Descriptor Table (GDT) or the Local Descriptor Table (LDT), contains the desired descriptor. Furthermore, each task may have its own LDT.
The intermediate address location of the base of the current LDT is specified by the LDT base register, which is identified by the currently active task, which is specified by the current task state descriptor, which is identified by the task state register. The intermediate address location of the base of the GDT is specified by a GDT Base Register. The Index is used to provide an offset to the desired descriptor relative to the base of the indicated table. The 13-bit Index can reference 2.sup.13, or 8,192 descriptors. For interrupts, an Interrupt Descriptor Table (IDT) is indexed using a scaled version of the interrupt vector to provide an offset to the desired descriptor within the IDT.
To reference a segment, the Index and Table Indicator must be loaded into a segment register. Any time an x86 instruction implicitly or explicitly changes any of the segment registers, the Index and TI are used to load the segment base and limit into programmer hidden registers (hereinafter referred to as "descriptor registers") from the descriptor tables stored in the memory/cache subsystem (hereinafter sometimes referred to as the "memory"). Once the segment base and limit are loaded for the associated segment, the Index and TI are no longer used. If the Index and TI are both zero there is no associated segment.
Intersegment changes in control flow always involve a change in the segment register. The segment register is loaded and the descriptor read from memory as prerequisites to adding any Offset to the segment base address. Virtual register file techniques are used to hold the segment's Index, TI, and the descriptor information. Separate virtual register files are used for the segment Index/TI combination, segment base addresses, and limits. When instructions implicitly or explicitly refer to an offset within a particular segment, the address of the associated segment register will specify the particular segment. This address is used to read the segment base address for routing to the relocation adder, discussed next.
Collectively, the GDT Base Register, Task State Register, active Task State Descriptor, active Local Descriptor Table Descriptor, Segment Index, Table Indicator, Segment Descriptor (particularly the base address, segment limit, B, D, and G bits), and Offset can be viewed as a programmer's virtual (logical) address. This view is accurate because all of this state information may affect the resulting intermediate and physical addresses.
The segment base address is added to the Offset to generate the corresponding intermediate address. The adder used is often referred to as the relocation adder. The adder effectively relocates all locations within the segment to an area in the intermediate address space that begins at the segment base address. Note that only the Offset and the segment base address participate in the addition. The Index and Table Indicator, previously used to obtain the segment base address, do not participate in the relocation addition.
Overview of Address Generation in the X86 Architecture
The process of generating addresses can be split into three basic conceptual steps.
In the first step, various general purpose register values and displacement values are added together to form an "Effective Address". The x86 architecture provides addressing modes that combine base registers, index registers (possibly scaled by an operand size) and various sized displacements. Combinations of one or more of these components can be specified, and the result is termed the "Effective Address" or "Offset" (the term used above).
In the second step, the effective address can be adjusted according to a "Base and Bounds" segmentation process. The segmentation process involves relocating the effective address by adding it to a "Segment Base" value, and comparing the effective address against a "Segment Limit" value to prevent unrestricted access to operands in other segments. The resulting address is called an "Intermediate Address".
In the third step, the intermediate address is translated to a "Physical Address" via a two-level memory-resident lookup table. The process of translating an intermediate address to a physical address when paging is enabled is called "Paging".
The following is a conceptual description of the paging process defined by the x86 architecture. The Paging process breaks the 32-bit intermediate and physical address spaces into collections of small, fixed sized blocks called "Pages". The size of a Page in the x86 architecture is 4096 bytes, and a Page is always aligned on a 4096-byte boundary. A Page in the intermediate address space is called a "Virtual" page. A Page in the physical address space is called a "Physical Page". The base address of a Physical Page is called the Page Frame Address.
Paging involves using the intermediate address to access a two-level table structure which maps a Virtual Page to a Physical Page. The tables are stored in memory. (A Translation Lookaside Buffer (TLB) may be available to cache recent virtual page to physical page translations, and to thereby obviate the need for accessing the two-level table structure in memory for some translations. When a TLB is available, the required Page Frame Address is always retrieved from the TLB. If necessary, the required Page Frame Address will first be retrieved from the two-level table structure in memory and stored into an entry of the TLB. The presence of a TLB will, hereinafter, be assumed. However, the presence of the TLB is not essential to the invention disclosed herein.)
A first level table is called a Page Directory, and each of its entries is called a Page Directory Entry (PDE). The Page Directory is itself a 4096-byte block aligned on 4096 byte boundary, and may be thought of as occupying a Physical Page. Each PDE is four bytes in size and contains the base address of a Page Table (20 bits), a Valid bit, an Accessed bit, several Protection bits, and several Attribute bits.
The base address of the currently active Page Directory is given by a dedicated register called CR3. Each separate task (or process) may have a unique Page Directory, allowing each task to have its own virtual to physical address mapping.
Each of the second level tables is called a Page Table, and each of its entries is called a Page Table Entry. The Page Table is also a 4096-byte block aligned on a 4096-byte boundary, and can be thought of as occupying a Physical Page. Each PTE is four bytes in size and contains the base address of a Physical Page (i.e. a 20-bit Page Frame Address), a Valid bit, an Accessed bit, a Dirty bit, several Protection bits, and several Attribute bits. The base address of a Page Table is given by a valid PDE.
If the Valid bit of a PDE is not asserted, then the remaining fields of the PDE are undefined, and no second level table is currently available for the requested intermediate address. Similarly, if the Valid bit of a PTE is not asserted, then the remaining fields of the PTE are undefined, and no physical Page Frame is currently available for the requested intermediate address. In either of these cases, the instruction that generated the address is aborted (faulted) and a Page Fault Exception is signaled to the operating system.
The Protection bits of the PDE are compared against the current privilege level of the processor and against the type of memory reference being made. The Protection bits of the PTE are similarly compared. If either of these checks results in a protection violation, the instruction that generated the address is aborted (faulted) and a Page Fault Exception is signaled.
The intermediate address is broken into three portions. Bits [31:22] are used as an index into the Page Directory. Bits [21:12] are used as an index into the Page Table. Bits [11:0] are used as the index into the selected Physical Page (the Page Frame), and are also called the Page Offset. Thus, every intermediate address and corresponding physical address share the same 12 least significant bits.
In addition, the operating system can disable the paging process by clearing a control register bit (i.e. CRO.PG). In this case the most significant 20 bits of the Intermediate Address become the Page Frame Address without translation.
In summary, the conceptual steps performed in translating an intermediate address when paging is enabled are as follows. The CR3 register is combined with bits [31:22] of the intermediate address and the selected PDE is read from memory. The PDE Valid and Protection bits are checked and a Page Fault Exception is signaled if necessary. The Base of the Page Table (extracted from the PDE) is then combined with bits [21:12] of the intermediate address and the selected PTE is read from memory. The PTE Valid and Protection bits are checked and a Page Fault Exception is signaled if necessary. The Page Frame Address is extracted from the PTE, and combined with bits [11:0] of the intermediate address to form the full 32 bit Physical Address.
Caching Segment Descriptors
Various instructions (hereinafter referred to as "segment selector load instructions") cause a segment descriptor to be loaded into a descriptor register. There are three types of segment selector load instructions (corresponding to the type of the segment whose descriptor is loaded): code segment load (i.e. a far branch instruction specifying a branch to a location outside the current code segment), (non-stack) data segment load, and stack segment load. A segment selector load instruction specifies a 16-bit selector to be loaded into a segment register. Bits [15:3], [2], and [1:0] of the selector store a 13-bit (Segment) Index, a 1-bit (Segment) Table Indicator (TI), and a 2-bit Requestor Privilege Level (RPL), respectively. The particular segment descriptor to be loaded is identified using the 13-bit (Segment) Index and the 1-bit (Segment) Table Indicator (TI), as described above.
One technique for obtaining the required segment descriptor involves the retrieval, from the appropriate descriptor table in memory (either the LDT for the current task or the GDT, depending on the TI bit of the specified selector), of the segment descriptor located at the intermediate address given by the sum of the base intermediate address of the descriptor table (which is stored either in the current LDT Base Descriptor or in a GDT Base Register) and 8 times (since each descriptor occupies 8 bytes) the value stored in the Index field of the specified selector. The obtained intermediate address for the descriptor must be translated into a corresponding physical address, as described above, before retrieval of the descriptor from memory can occur.
An alternative technique involves the use of a descriptor cache for storing segment descriptors recently retrieved from memory. In this technique, the descriptor cache is searched for the required segment descriptor. If it is found, the segment descriptor is loaded from the descriptor cache into the appropriate hidden descriptor register (thereby avoiding a relatively time consuming access to a segment descriptor table in memory). If not present in the descriptor cache, the required segment descriptor is retrieved from memory in the manner discussed above. One type of segment descriptor cache is disclosed in UK Patent Application 2,260,629 (hereinafter "the INTEL patent application"), entitled "A Segment Descriptor Cache for a Microprocessor".
One issue introduced by the use of a descriptor cache is memory-cache coherence. In particular, given that sometimes programs change the contents of descriptor tables in memory, there is a need for some scheme that maintains coherence between the contents of the descriptor tables and the contents of the descriptor cache. Only with such a scheme, can the descriptor cache be relied upon to substitute for an access to a descriptor table in memory. (The Intel patent application does not disclose a scheme for maintaining coherence between the memory and descriptor cache.)
Somewhat extensive checking must be performed when loading a hidden descriptor register with a segment descriptor from memory. The checking involves comparisons between the current privilege level (i.e. the privilege level at which the selector load instruction is executing), the descriptor privilege level (a field of the descriptor, indicating the least privileged level at which a task may access the descriptor and the segment associated with the descriptor) and the requestor privilege level (i.e. bits [1:0] of the selector). The detailed description section of U.S. Pat. No. 4,442,484, entitled "Microprocessor Memory Management and Protection Mechanism", describes an example of the above checking. What would be desirable is a technique, to be used in conjunction with a descriptor cache, that takes advantage of the fact that the extensive checking was originally satisfied when a descriptor was loaded into the descriptor cache (and a hidden descriptor register) and thereby simplifies the condition checking performed before a hidden descriptor register is subsequently loaded with the same segment descriptor from the descriptor cache.